Leetcode刷题记录(Java)

Problem 107 Binary Tree Level Order Traversal II

该问题属于二叉树遍历问题,需要从底部向顶部遍历,每一层数据保存在一个list中

主要思路:
由于需要进行层序遍历,即记录每层信息,所以采用广度优先遍历,最后再对每层数据倒序输出即可.故首先创建一个map,并且实现其内部排序类,这样就能根据每层的index倒序排列.
接下来就是分为两种情况:

结点不存在
结点存在

对于这两种情况:

不存在结点则直接返回空的ArrayList而不是返回null
若存在结点则有两种情况:
- 该结点为它所在层的第一个元素,此时需要创建ArrayList,并将该结点放入,之后将ArrayList存入map,之后就是对该结点的左右子树进行递归访问
- 该结点不是它所在层的第一个元素,此时从map中通过层数key取到它所在层的ArrayList,并将该结点加入ArrayList中,更新map

注意事项:

在递归子树之后注意将层数-1以回到上层
注意排序问题

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int i=0;
    private TreeMap<Integer,List<Integer>> map = new TreeMap<Integer, List<Integer>>(
        new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return  o2.compareTo(o1);
            }
        }
    );
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        i+=1;
        if(root==null){
            return new ArrayList<>();
        }else{
            List<Integer> list = map.get(i);
            if(list == null){
                list = new ArrayList<>();
                list.add(root.val);
                map.put(i,list);
                levelOrderBottom(root.left);
                i=i-1;
                levelOrderBottom(root.right);
                i=i-1;
            }else {
                list.add(root.val);
                map.put(i,list);
                levelOrderBottom(root.left);
                i=i-1;
                levelOrderBottom(root.right);
                i=i-1;
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        Set<Integer> keySet = map.keySet();
        for (int key : keySet) {
            result.add(map.get(key));
        }
        return result;
    }
}

⭐Problem 206 Reverse Linked List

该问题属于在链表中经典的链表反转问题,一般对于反转问题,不论是链表反转、字符串反转还是其他常见的反转问题,一般来说会有两种常规思路,一种是递归法,另一种就是循环遍历,两种方法各有优劣,个人偏向于递归,其代码看起来更加优雅,不需要各种循环.

主要思路:
该问题分为以下几种情况:

链表为空或为单值链表则直接返回head
链表含有2个或以上元素,则利用递归进行压栈实现链尾的元素变成头结点.

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode temp = head.next;
        ListNode newHead = reverseList(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }
}

代码解释:
以1->2->3->4->5->null为例,我们来分析下代码流程

最开始head为1号结点时进入函数,判断其以及其后一个结点是否为null,判断为否则进入ListNode temp = head.next;此时temp为2号结点,随后进入递归,此时的head为2号结点
重复上述操作,temp为3号结点,继续递归,head为3号结点
重复上述操作,temp为4号结点,继续递归,head为4号结点
重复上述操作,temp为5号结点,继续递归,head为5号结点
当到达5号结点后,其next结点为null,则返回5号结点,也就是说此时newHead为5号结点
然后运行到temp.next = head;注意此时的head已经回退到了4号结点,因为5号已经出栈,成为了newHead.也就是说现在成了5->4,之后运行head.next = null,即5->4->null,随后返回newHead,也就是5号结点.
继续运行temp.next = head;此时的temp已经是4了,而head为3,故在局部形成了4->3->null,至于返回值仍旧是newHead,也就是5号结点,因为其在上轮已经形成了5->4的链,所以此处成为5->4->3->null
继续运行temp.next = head;此时的temp已经是3了,而head为2,故在局部形成了3->2->null,至于返回值仍旧是newHead,也就是5号结点,因为其在之前已经形成了5->4的链,所以此处成为5->4->3->2->null
继续运行temp.next = head;此时的temp已经是2了,而head为1,故在局部形成了2->1->null,至于返回值仍旧是newHead,也就是5号结点,因为其在之前已经形成了5->4的链,所以此处成为5->4->3->2->1->null,反转完成.

对于遍历法从人的直观理解上来说更加简单,因为它是一个顺向思维
代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

代码解释:
以1->2->3->4->5->null为例,我们来分析下代码流程
首先使用pre存储当前结点,用next作为临时变量

1号结点进入循环,此时next为2号结点,head.next为null,pre为1号结点,head为2号结点
2号结点进入循环,此时next为3号结点,head.next=pre,即2->1,此时pre为2号结点,head为3号结点
3号结点进入循环,此时next为4号结点,head.next=pre,即3->2,此时pre为3号结点,head为4号结点
4号结点进入循环,此时next为5号结点,head.next=pre,即4->3,此时pre为4号结点,head为5号结点
5号结点进入循环,此时next为null,head.next=pre,即5->4,此时pre为5号结点,head为null,故退出循环
最后返回pre,也就是5号结点

Problem 235 Lowest Common Ancestor of a Binary Search Tree

该问题属于找寻二叉树两结点最近共同祖先问题,由于题目已经做了很多限制,比如两个结点一定在树中且该树为二叉搜索树.此时就可以直接利用二叉搜索树的性质进行查找.

主要思路:
该问题共有以下几种情况:

待查找结点p和q的值分列root两侧(利用二叉搜索树性质,若值小于root必在其左侧,大于root必在其右侧),或者p或q的值与root相等(即要查找的p或q就是root),则直接返回root
待查找结点p和q的值位于root子树某侧,则对其左右子树进行递归查找

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flag = true;
    TreeNode tempRoot = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }else if(((p.val>root.val&&q.val<root.val)||(p.val<root.val&&q.val>root.val)||p.val==root.val||q.val==root.val)){
            flag = false;
            return root;
        }
        if(flag){
            tempRoot = lowestCommonAncestor(root.left,p,q);
        }
        if(flag){
            tempRoot = lowestCommonAncestor(root.right,p,q);
        }
        return tempRoot;
    }
}

Problem 242 Valid Anagram

该问题就是检查两个字符串每类字母数量是否相同,其实这个问题很简单,很多方法都能解决,比如可以直接对字符串排序,最后比较两字符串是否相等,但是该方法和排序复杂度直接相关,比如我使用最简单的冒泡排序进行暴力求解结果超时.后转而使用map进行统计,该方法可以满足时间复杂度要求,但是整体速度较慢.最后使用了位置推导的方法进行判断,大大降低了时间复杂度。

主要思路:
由于字符串可以拆解成字符数组,而这时就可以利用ASCII码的排列关系进行计算,可以先建立一个长度为26的字符数组,然后将字符串拆解成的字符数组中每个字符与97相减,这样就能与0-25匹配,比如原本为b的字符,相减后为1,则将新字符数组1号位置数值加1,这样单次循环后就能将每个字母的频次统计出来,最后再次用单次循环就能比较出结果.
这种新建数组之后按照位置统计的思想在很多相似类型题目中都有涉及

代码实现:

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] c = new int[26];
        int[] c2 = new int[26];
        
        for(int n:s.toCharArray())
            c[n-97]++;
        for(int n:t.toCharArray())
            c2[n-97]++;
        for(int i=0;i<c.length;i++)
            if(c[i] != c2[i])
                return false;
        return true;
    }
}